package leetcode.每日一题;

import org.junit.Test;

import java.util.*;

/**
 * @author ：zsy
 * @date ：Created 2021/12/5 12:22
 * @description：https://leetcode-cn.com/problems/super-pow/
 */
public class 超级次方 {
    @Test
    public void test() {
        Solution solution = new Solution();
        System.out.println(solution.superPow(Integer.MAX_VALUE, new int[]{1, 2, 3, 4, 5}));
    }

    // 递归
    /*
    class Solution {
        private int MOD = 1337;

        public int superPow(int a, int[] b) {
            return dfs(a, b, b.length - 1);
        }

        private int dfs(int a, int[] b, int i) {
            if (i == -1) return 1;
            return pow(dfs(a, b, i - 1), 10) * pow(a, b[i]) % MOD;
        }

        private int pow(int a, int b) {
            int ans = 1;
            a = a % MOD;
            while (b-- > 0) ans = ans * a % MOD;
            return ans;
        }
    }
     */

    class Solution {
        private int MOD = 1337;

        public int superPow(int a, int[] b) {
            return dfs(a, b, b.length - 1);
        }

        private int dfs(int a, int[] b, int i) {
            if (i == -1) return 1;
            return quick_pow(dfs(a, b, i - 1), 10) * quick_pow(a, b[i]) % MOD;
        }

        private int quick_pow(int a, int b) {
            int ans = 1;
            a = a % MOD;
            while (b != 0) {
                if ((b & 1) != 0) ans = a * ans % MOD;
                a = a * a % MOD;
                b >>= 1;
            }
            return ans;
        }

    }

}
